package algorithms.paixu;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

/**
 * @功能
 * @创建时间 2020/12/15
 * fastmerge
 */
public class Merge2 {
    private static Comparable[] aux;
    public static int ArrayAccessTimes=0;
    public static void sort(Comparable[] a)
    {
        aux=new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable[] a,int lo,int hi)
    {
        if (hi<=lo) return;
        int mid=lo+(hi-lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        ArrayAccessTimes++;
        merge(a,lo,mid,hi);
    }

    public static void merge(Comparable[] a,int lo,int mid,int hi)
    {

        int i=lo,j=hi;
        for (int k=lo;k<=mid;k++)
            aux[k]=a[k];
        /*
       //k 索引更容易理解的方式
        for (int k=0;mid+1+k<=hi;k++)
               aux[mid+1+k]=a[hi-k];
        */
        for (int k=mid+1;k<=hi;k++)
            aux[k]=a[hi-k+mid+1];


        for(int k=lo;k<=hi;k++)
            if (less(aux[j],aux[i])) a[k]=aux[j--];
            else                           a[k]=aux[i++];
    }
    private static boolean less(Comparable v,Comparable w)
    { return v.compareTo(w)<0;}

    public static boolean isSorted(Comparable[] a)
    {
        for(int i=1;i<a.length;i++)
            if(less(i,i-1)) return false;
        return true;
    }

    public static void main(String[] args)
    {
        int N=Integer.parseInt(args[0]);
        Double[] a=new Double[N];
        for(int i=0;i<N;i++)
            a[i]= StdRandom.uniform();
        sort(a);

        StdOut.printf("isSorted=%s",isSorted(a));
    }
}
